package com.atwulidun.dynamicprogramming03.knapsackproblem.unrefined;

import java.util.Arrays;
// 对于0-1背包(未进行空间优化)：
// 问题描述：
// 一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
// 状态转移方程：dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i])

public class ZeroOneKnapsackProblem {
    // 物体的重量
    private static int[] w = {1, 4, 3};
    // 物体的价值
    private static int[] v = {1500, 3000, 2000};
    // 背包的最大容量
    private static int maxWeight = 7;
    // 前i个物体能装入背包容量为j时的最大价值
    // 行代表第几个物体，列代表背包的容量
    private static int[][] dp = new int[w.length + 1][maxWeight + 1];
    // 记录背包装入的物体，与dp维度相同
    private static int[][] path = new int[w.length + 1][maxWeight + 1];


    public static void main(String[] args) {
        // 对dp进行初始化，第一行和第一列全为0
        // 第一行置为0
        Arrays.fill(dp[0], 0);
        // 第一列置为0
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }

        // 动态地将物品装入背包
        // 外层循环控制物体
        for (int i = 1; i < dp.length; i++) {
            // 内层循环控制背包容量
            for (int j = 1; j < dp[0].length ; j++) {
                // 如果当前物品的重量大于当前背包最大的容量
                // 注意：w的下标是从0开始，这里要减个1
                if (w[i - 1] > j) {
                    // 使用前i-1个物品的装入策略
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 如果当前物品的重量小于等于当前背包的最大容量，这时要比较：
                    // 前i-1个物品的装入策略；装入当前物品，同时剩余空间再装前i-1个物品
                    // 注意：v的下标也是从0开始，故这里也要-1
                    if (dp[i - 1][j] < v[i - 1] + dp[i - 1][j - w[i - 1]]) {
                        dp[i][j] = v[i - 1] + dp[i - 1][j - w[i - 1]];
                        // 同时把path对应当前的dp[i][j]标记为1
                        path[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }

        // 对dp进行逆向遍历
        int i = path.length - 1;// 表示最后一件物体
        int j = path[0].length - 1;// 表示背包的最大容量
        while (i > 0 && j > 0) {
            // 如果背包的最大容量装入的是最后一件物体
            if (path[i][j] == 1) {
                System.out.println("第" + i + "件物品装入背包");
                j -= w[i - 1];// 求出剩余的空间
            }
            // 这里分两种情况：
            // 1.如果上面的if成立，那么i--是看剩余的空间是否装入了前一件物品
            // 2.如果上面的if不成立，那么i--是看当前空间是否装入了前一件物品
            i--;
        }
        for (int[] ints : dp) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
        for (int[] ints : path) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}
